package elementaryAlgorithm;


import java.util.ArrayList;
import java.util.List;

/**
 * @author 郭辉
 * @className TODO
 * @description 51. N 皇后
 * 按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。
 *
 * n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
 *
 * 给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。
 *
 * 每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。
 *
 *
 *
 * 示例 1：
 *
 *
 * 输入：n = 4
 * 输出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
 * 解释：如上图所示，4 皇后问题存在两个不同的解法。
 * 示例 2：
 *
 * 输入：n = 1
 * 输出：[["Q"]]
 *
 *
 * 提示：
 *
 * 1 <= n <= 9
 * 通过次数292,963提交次数395,110
 * @date 2023/3/30 20:05
 * @company 海康威视
 * @since 1.0.0
 */
public class Leet51 {
    public List<List<String>> solveNQueens(int n) {
        //初始化棋盘
        List<List<String>> res = new ArrayList<>();
        List<List<Character>> board = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            List<Character> list = new ArrayList<>();
            for (int j = 0; j < n; j++) {
               list.add('.');
            }
            board.add(list);
        }
        NQueens(board,0,res);
        return res;
    }

    //返回条件
    //路径
    //选择
    public void NQueens(List<List<Character>> board ,int row,List<List<String>> res){
        //结束条件
        if (row >= board.size()){
            List<String> tem = new ArrayList<>();
            String s="";
            for (int i = 0; i < board.size(); i++) {
                for (int j = 0; j < board.get(i).size(); j++) {
                    s += board.get(i).get(j);
                }
                tem.add(s);
                s = "";
            }
            res.add(tem);
            return;
        }

        for (int i = 0; i < board.size(); i++) {
            //剪枝
            if (!isValid(board,row,i)){
                continue;
            }
            //做选择
            board.get(row).set(i,'Q');
            NQueens(board,row + 1,res);
            //撤销选择
            board.get(row).set(i,'.');
        }
    }

    private boolean isValid(List<List<Character>> board, int row, int col) {
        //同行，同列，同斜线
        for (int i = 0; i < board.size(); i++) {
            if (board.get(row).get(i) == 'Q'){
                return false;
            }
        }
        for (int i = 0; i < board.size(); i++) {
            if (board.get(i).get(col) == 'Q'){
                return false;
            }
        }
        //右上，左下，右下
        //左上，
        int offset = col - row;
        for (int i = 0; i < board.size(); i++) {
            if (i+offset >=0 && i+offset <board.size() && board.get(i).get(i + offset) == 'Q'){
                return false;
            }
        }
        offset = col + row;
        for (int i = 0; i < board.size(); i++) {
            if (offset -i < board.size() && offset -i >= 0 && board.get(i).get(offset -i) == 'Q'){
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        Leet51 leet51 = new Leet51();
        List<List<String>> lists = leet51.solveNQueens(8);
        System.out.println(lists);
    }
}
